package com.github.kezhenxu94.playground.java.sorting;

public class HeapSort {

	public void sort(int[] array) {
		int len = array.length;
		buildMaxHeap(array, len);
		for (int i = len - 1; i > 0; i--) {
			ArrayUtil.swap(array, 0, i);
			heapMaxify(array, 0, --len);
		}
	}

	private void buildMaxHeap(int[] array, int len) {
		for (int i = len / 2; i >= 0; i--)
			heapMaxify(array, i, len);
	}

	private void heapMaxify(int[] array, int i, int len) {
		int leftIndex = i << 1;
		int rightIndex = leftIndex + 1;
		int largestIndex = i;
		if (leftIndex < len && array[leftIndex] > array[largestIndex])
			largestIndex = leftIndex;
		if (rightIndex < len && array[rightIndex] > array[largestIndex])
			largestIndex = rightIndex;
		if (largestIndex != i) {
			ArrayUtil.swap(array, largestIndex, i);
			heapMaxify(array, largestIndex, len);
		}
	}
}
